package dramsy_christian_bellamn_floyd;

/**
 *
 * @author <a href="mailto:christian.dramsy@gmail.com">DRAMSY Christian</a>
 */
public class Floyd {

    private Graphe graphe;

    public Floyd(Graphe graphe) {
        this.graphe = graphe;
    }

    /**
     * Calcul le plus court chemin par la methode de Floyd
     */
    public void plusCourtChemin() {
        if (this.graphe.isOriented()) {
            System.out.println("Error Floyd : Le graphe DOIT être non orienté");
            return;
        }
        int INFINI = 10000000;
        int ordre = this.graphe.getOrdre();
        //  Matrice contenant la valeur du plus court chemin
        int[][] d = new int[ordre][ordre];
        int[][] pred = new int[ordre][ordre];
        int i, j, k;
        int min;
        for (i = 0; i < ordre; i++) {
            for (j = 0; j < ordre; j++) {
                d[i][j] = (this.graphe.getMatriceAdjValue(i, j) != 0) ? this.graphe.getMatriceAdjValue(i, j) : INFINI;
            }
            d[i][i] = 0;
        }

        for (i = 0; i < ordre; i++) {
            for (j = 0; j < ordre; j++) {
                pred[i][j] = i;
            }
        }

        for (k = 0; k < ordre; k++) {
            for (i = 0; i < ordre; i++) {
                for (j = i + 1; j < ordre; j++) {
                    min = (d[i][j] < d[i][k] + d[k][j]) ? d[i][j] : d[i][k] + d[k][j];
                    int old = d[i][j];
                    d[i][j] = d[j][i] = min;

                    //  Si d[i][j] a été modifié
                    if (old != d[i][j]) {
                        pred[i][j] = pred[k][j];
                        pred[j][i] = pred[k][i];
                    }
                }
            }
        }
        System.out.println();
        UtilitaireAffichage.displayMatrice(pred);
        System.out.println();
        UtilitaireAffichage.displayMatrice(d);
    }
}
